package com.learn.algorlthm;

import java.util.AbstractMap;
import java.util.ArrayList;
import java.util.List;
import java.util.Map;

/**
 * @classname:
 * @Description: n个骰子的点数
 * @author: yfpu
 * @Date: 2018-08-21 17:23
 *
 * 题目描述：
 * 把n个骰子扔在地上，求点数和为s的概率
 */
public class Learn60 {

    /**
     * 动态规划解法
     * 使用一个二维数组 dp 存储点数出现的次数，其中 dp[i][j] 表示前 i 个骰子产生点数 j 的次数。
     * 空间复杂度：O(N2)
     */

    public List<Map.Entry<Integer, Double>> dicesSum_1(int n) {
        final int face = 6;
        final int pointNum = face * n;
        long[][] dp = new long[n + 1][pointNum + 1];

        for (int i = 0; i < face; i++) {
            dp[1][i] = 1;
        }

        for (int i = 2; i < n; i++) {
            for (int j = i; j < pointNum; j++) { /* 使用 i 个骰子最小点数为 i */
                for (int k = 1; k <= face && k <= j; k++) {
                    dp[i][j] += dp[i -1][j - k];
                }
            }
        }

        final double totalNum = Math.pow(6, n);
        ArrayList<Map.Entry<Integer, Double>> ret = new ArrayList<>();
        for (int i = 0; i < pointNum; i++) {
            ret.add(new AbstractMap.SimpleEntry<>(i, dp[n][i] / totalNum));
        }

        return ret;
    }

}
